dual matroid について

has a basis set disjoint from it.〔.〕〔.〕〔.〕
Matroid duals go back to the original paper by Hassler Whitney defining matroids.〔. Reprinted in , pp. 55–79. See in particular section 11, "Dual matroids", pp. 521–524.〕 They generalize to matroids the notions of planar graph duality and of dual spaces in linear algebra.
==Basic properties==
Duality is an involution: for all

M

(M^\ast)^\ast=M

.〔〔〔
An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of

M

. The basis exchange axiom, used to define matroids from their bases, is self-complementary, so the dual of a matroid is necessarily a matroid.〔
The flats of

M

are complementary to the cycles (unions of circuits) of

M^\ast

, and vice versa.〔
If

r

is the rank function of a matroid

M

on ground set

E

, then the rank function of the dual matroid is

r^\ast(S)=r(E \setminus S)+|S|-r(E)

.〔〔〔

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「dual matroid」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース